package com.arron.algorithm.sort;


/**
 * 冒泡排序
 *
 *  时间复杂度：
 *      平均时间复杂度：
 *      最坏时间复杂度：
 *  空间复杂度
 *
 */
public class BubbleSort {


    public static void main(String[] args) {

        int[] array = {2,3,1,0,98};

        long timeMillis = System.currentTimeMillis();
        sort2(array);
        // sort(array);
        System.out.println("============耗时："+(System.currentTimeMillis()-timeMillis));
        print(array);

    }


    /**
     * 升序
     * 最坏时间复杂度和平均都是 O（n2）
     * @param array
     */
    public static void sort(int[] array){

        if (array == null || array.length<1){
            return;
        }

        int temp = 0;
        for (int i = 0; i < array.length; i++) {

            for (int j = 0; j < array.length-i-1; j++) {

                if (array[j+1]<array[j]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }

            }
        }

    }


    /**
     * 改进，如果原本就有序，就直接返回
     * @param array
     */
    public static void sort2(int[] array){
        if (array == null || array.length<2){
            return;
        }

        int temp = 0;

        // 记录最后一次交换时的位置
        int lastswap = array.length - 1;

        for (int i = 0; i < array.length; i++) {
            int singal = lastswap;
            for (int j = 0; j < array.length-i-1; j++) {

                if (array[j+1]<array[j]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    lastswap = j;
                }

            }
            if (singal == lastswap){
                //如果第一轮没有发生交换代表有序，则直接跳出循环
                break;
            }
        }

    }

    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }


}
